home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / pc / files / dsp / 96000tar.z / 96000tar / 96000 / cfft1-96.asm next >
Assembly Source File  |  1992-04-28  |  14KB  |  250 lines
  1. ;    Memory Size: Prog:  141 words ; Data:  5120 words
  2. ;    Number of clock cycles:     41916 (20958 instruction cycles)   1024 pt.
  3. ;                             91626                              2048 pt.
  4. ;                            199194                              4096 pt.
  5. ;                            430666                              8192 pt.
  6. ;                            926330                             16384 pt.
  7. ;
  8. ;    Clock Frequency:     40.0MHz
  9. ;    Instruction cycle time:     50.0ns
  10. ;
  11. ;    
  12. ;**************************************************************************
  13. ; Motorola DSP Operations  28 February 1992                                
  14. ;**************************************************************************
  15. ;
  16. ; Complex, Radix 2 Cooley-Tukey Decimation in Time FFT
  17. ; Untested
  18. CFFT1     macro     points,passes,data,coef,coefsize,odata
  19. CFFT1     ident 1,2
  20. ;
  21. ; Faster FFT using Programming Tricks found in Typical FORTRAN Libraries
  22. ;
  23. ;      First two passes combined as a four butterfly loop since
  24. ;            multiplies are trivial.
  25. ;            2.25 cycles internal (4 cycles external) per Radix 2 
  26. ;            butterfly.
  27. ;      Middle passes performed with traditional, triple-nested DO loop.
  28. ;            4 cycles internal (8 cycles external) per Radix 2 butterfly
  29. ;            plus overhead.  Note that a new pipelining technique is 
  30. ;            being used to minimize overhead.
  31. ;      Next to last pass performed with double butterfly loop.
  32. ;            4.5 cycles internal (8.5 cycles external) per Radix 2
  33. ;            butterfly.
  34. ;      Last pass has separate single butterfly loop.
  35. ;            5 cycles internal (9 cycles external) per Radix 2 
  36. ;            butterfly.
  37. ;
  38. ;      For 1024 complex points, average Radix 2 butterfly = 3.8 cycles
  39. ;      internal and 7.35 cycles external, assuming a single external
  40. ;      data bus.
  41. ;
  42. ;      Because of separate passes, minimum of 32 points using these
  43. ;      optimizations.  Approximately 150 program words required. 
  44. ;      Uses internal X and Y Data ROMs for twiddle factor coefficients
  45. ;      for any size FFT up to 1024 complex points.
  46. ;
  47. ;      Assuming internal program and internal data memory (or two
  48. ;      external data buses, 1024 point complex FFT is 1.57 msec at 
  49. ;      75 nsec instruction rate.  Assuming internal program and 
  50. ;      external data memory, 1024 point complex FFT is 2.94 msec 
  51. ;      at 75 nsec instruction rate.
  52. ;
  53. ; First two passes
  54. ;
  55. ;      9 cycles internal, 1.77X faster than 4 cycle Radix 2 bfy
  56. ;      16 cycles external, 2.0X faster than 4 cycle Radix 2 bfy
  57. ;
  58. ;      r0 = a pointer in & out
  59. ;      r6 = a pointer in at first two passes then points to twiddle factor
  60. ;      r4 = b pointer in & out
  61. ;      r1 = c pointer in & out
  62. ;      r5 = d pointer in & out
  63. ;      n5 = 2
  64. ;         r2 = start base of input data of all passes, change at last pass
  65. ;
  66. ;      normally ordered input data
  67. ;      normally ordered output data
  68. ;
  69.       move      #points,d1.l        ;number of FFT input data
  70.       move      #passes,d9.l        ;passes=log2(points)
  71.       move      #data,d0.l            ;input data start location
  72.       move      #coef,m2            ;twiddle factor start location if DE=0
  73.                                             ;otherwise use internal sin and cos table 
  74.       move      #coefsize,d2.l    ;size of twiddle factor=points/2
  75.  
  76.       lsr      d1     d0.l,r0        ;d1=points/2,     r0 points to base of input data 
  77.       lsr      d1     r0,r2        ;d1=points/4,        r2=base of input data
  78.       add      d1,d0  d1.l,d8.l    ;d0=point to b,     d8=points/4
  79.       add      d1,d0  d0.l,r4        ;d0=pointer to c, r4 points to b
  80.       add      d1,d0  d0.l,r1        ;d0=pointer to d, r1 points to c
  81.       lsr      d2     d0.l,r5        ;d2=points/4,     r5 points to d
  82.       lsr      d2     r0,r6        ;d2=points/8,        r6 points to a
  83.       move     #2,n5                    ;n5=2
  84.       move     d2.l,n6                ;n6=points/8
  85.       move     #-1,m0                ;linear address r0
  86.       move     m0,m1                    ;linear address r1
  87.       move     m0,m4                    ;linear address r4
  88.       move     m0,m5                   ;linear address r5
  89.       move     m0,m6                   ;linear address r6
  90.  
  91.       move     x:(r0),d1.s            ;d1=ar
  92.       move     x:(r1),d0.s       ;d0=cr      
  93.       move     x:(r5)-,d2.s      ;d2=dr      
  94.       move     y:(r5)+,d4.s      ;d4=the last data in ci,since di' is calculated at last, no slot for writing di' 
  95.                                             ;in current interation. See _twopass loop line 5 (l5) below.
  96.       faddsub.s  d1,d0   x:(r4),d5.s  ;d5=br,d1=ar-cr,d0=ar+cr             
  97.       faddsub.s  d5,d2   y:(r4),d7.s  ;d7=bi,d5=br-dr,d2=br+dr 
  98. ;
  99. ;      Combine first two passes with trivial multiplies.
  100. ;
  101.       do      d8.l,_twopass
  102.  
  103.       faddsub.s  d0,d2                y:(r5),d6.s         ;d6=di,d0=ar+cr-(br+dr)=br',d2=ar+cr+br+dr=ar' 
  104.       faddsub.s  d7,d6  d2.s,x:(r0)+  y:(r6)+,d3.s        ;d3=ai,d7=bi-di,d6=bi+di,                                         PUT ar'
  105.       faddsub.s  d1,d7  d0.s,x:(r4)   y:(r1)+,d2.s        ;d2=ci,d1=ar-cr-(bi-di)=dr',d7=ar-cr+(bi-di)=cr',        PUT br' 
  106.       faddsub.s  d3,d2  d1.s,x:(r5)-                    ;d3=ai-ci,d2=ai+ci,                                                 PUT dr' 
  107.       faddsub.s  d2,d6  x:(r0)-,d1.s  d4.s,y:(r5)+n5    ;d2=ai+ci-(bi+di)=bi',d6=ai+ci+bi+di=ai',d1=next ar,    PUT di'
  108.                                                                         ;(l5) at first last ci move in,in next itera. di' was put in
  109.       faddsub.s  d3,d5  x:(r1)-,d0.s  d2.s,y:(r4)+     ;d3=ai-ci-(br-dr)=ci',d5=ai-ci+(br-dr)=di',d0=next cr,PUT bi' 
  110.       faddsub.s  d1,d0  x:(r5),d2.s   d6.s,y:(r0)+     ;d1=nar-ncr,d0=nar+ncr,d2=ndr,                                PUT ai' 
  111.       ftfr.s     d5,d4  x:(r4),d5.s   d3.s,y:(r1)      ;d4=di',d5=nbr,                                                    PUT ci' 
  112.       faddsub.s  d5,d2  d7.s,x:(r1)+  y:(r4),d7.s       ;d5=nbr-ndr,d7=nbi                                                 PUT cr' 
  113. _twopass
  114.       move                            d4.s,y:-(r5)        ;PUT last di'               
  115. ;
  116. ; Middle passes
  117. ;
  118.       move     #4,d0.l                                            ;d0=4=group per pass
  119.       move     d9.l,d3.l                                        ;d3=number of passes (log2(points))
  120.       clr      d2         d8.l,d1.l                            ;d2=0,d1=points/4
  121.       sub      d0,d3      d2.l,m6                            ;m6=0 bit reverse on r6!!!,d3-d0=remaining loop times
  122.  
  123.       do      d3.l,_end_pass                ;do 6 times for 1024 points
  124.       move    d0.l,n2                        ;n2=4=number of group in a pass, n2=n2*2 after each pass 
  125.       move    r2,r0                            ;r0 points to first data A again 
  126.       lsr     d1 r2,r1                        ;d1=input A and B offset=points/8 first time, then divided by 2 at each pass
  127.         move       d1.l,n1                        ;n1=offset of input B,r1 inceased # of BF times in the _end_bfy loop
  128.         inc      d1    d1.l,d0.l                 ;d1=offset of A,A' and B'=# of BF +1, 
  129.       dec      d0    m2,r6                       ;r6 always points to 1st twidlle factor at each pass     
  130.         dec      d0    d1.l,n0                    ;d1=BF-2=loop # of BF,because BF kernel only loops BF-2 times for 96k     
  131.         move       d0.l,n3                                            ;n3=# of BF-2 in each group,n3=n3/2 after each pass
  132.       move    n0,n4                                                ;n0=offset of A, n4=offset of A'=# of BF +1,
  133.       move    n0,n5                                                ;n5=offset of B'
  134.       move      (r1)+n1                                           ;r1 points to B
  135.       move    r0,r4                                                ;r4 points to A'
  136.       move    r1,r5                                                ;r5 points to B'
  137.       move               x:(r6)+n6,d9.s y:,d8.s            ;d9=wr,d8=wi,twidlle with bit reverse addr. 
  138.       move                              y:(r1),d7.s    ;starts 3rd pass, all radix 2 BF,no c and d, d7=bi
  139.       fmpy.s  d8,d7,d3   x:(r1)+,d6.s                        ;d6=br,d3=bi*wi
  140.       fmpy.s  d9,d6,d0                                            ;d0=br*wr
  141.       fmpy.s  d9,d7,d1                  y:(r1),d7.s    ;d1=bi*wr,d7=next bi
  142.       fmpy    d8,d6,d2  fadd.s    d3,d0  x:(r0),d4.s    ;d2=br*wi,d0=bi*wi+br*wr,d4=ar
  143.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+,d6.s    ;d3=nbi*wi,d4=ar-(bi*wi+br*wr)=br',d0=ar+(bi*wi+br*wr)=ar',d6=nbr
  144.  
  145.       do      n2,_end_grp                                        ;do 4,8,16,.. groups in the pass
  146.  
  147.       do      n3,_end_bfy                                        ;do (points/8)-2,points/16,points/32,... BFs in each pass
  148.  
  149.       fmpy    d9,d6,d0  fsub.s    d1,d2  d0.s,x:(r5)  y:(r0)+,d5.s 
  150.                                                                         ;d0=nbr*wr,d1=bi*wr,d2=br*wi-bi*wr,d5=ai,                PUT ar' 
  151.       fmpy    d9,d7,d1  faddsub.s d5,d2  d4.s,x:(r4)  y:(r1),d7.s  ;d1=nbi*wr,d5=ai-(br*wi-bi*wr)=ai'
  152.                                                                         ;d2=ai+(br*wi-bi*wr)=bi',d7=nbi,                            PUT br'
  153.       fmpy    d8,d6,d2  fadd.s    d3,d0  x:(r0),d4.s  d2.s,y:(r4)+ 
  154.                                                                         ;d2=nbr*wi,d0=nbr*wr+nbi*wi,d4=nar,                        PUT bi'
  155.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+,d6.s d5.s,y:(r5)+ ;  d6=nbr;d4=nar-(nbr*wr+nbi*wi)=nbr', 
  156.                                                                         ;d3=nbi*wi,,d0=nar+(nbr*wr+nbi*wi)=nar',                PUT ai' 
  157. _end_bfy
  158.  
  159.       move      (r1)+n1                                            ;r1 points to b of the next group
  160.       fmpy    d9,d6,d0  fsub.s     d1,d2  d0.s,x:(r5)    y:(r0)+,d5.s
  161.                                                                         ;d0=nbr*wr,d1=nbi*wr,d2=nbr*wi-nbi*wr,d5=nai,      PUT nar' 
  162.       fmpy    d9,d7,d1  faddsub.s d5,d2  d4.s,x:(r4)    y:(r1),d7.s ;   d7=next group bi=ngbi,
  163.                                                                         ;d1=nbi*wr,d5=ai-(br*wi-bi*wr)=ai',d2=ai+(br*wi-bi*wr)=bi',  PUT nbr'
  164.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s    d2.s,y:(r4)+
  165.                                                                         ;d2=nbr*wi,d0=nbr*wr+nbi*wi,d4=nar,                                PUT nbi'
  166.       move                     x:(r6)+n6,d9.s y:,d8.s ;get another twiddle factor for next group, d9=wr,d8=wi
  167.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+,d6.s   d5.s,y:(r5)+ ;    d4=nar-(nbr*wr+nbi*wi)=nbr',
  168.                                                                         ;d3=nbi*wi,d0=nar+(nbr*wr+nbi*wi)=nar',                        PUT nai' 
  169.       fmpy    d9,d6,d0  fsub.s     d1,d2  d0.s,x:(r5)    y:(r0)+n0,d5.s
  170.                                                                         ;d0=nbr*wr,d1=nbi*wr,d2=nbr*wi-nbi*wr,d5=nai,                PUT ngar' 
  171.       fmpy    d9,d7,d1  faddsub.s d5,d2  d4.s,x:(r4)    y:(r1),d7.s
  172.                                                                         ;d1=nbi*wr,d5=ai-(br*wi-bi*wr)=ai',d2=ai+(br*wi-bi*wr)=bi', PUT ngbr'
  173.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s    d2.s,y:(r4)+n4 ; inc B output pointer
  174.                                                                         ;d2=nbr*wi,d0=nbr*wr+nbi*wi,d4=nar,                              PUT ngbi'
  175.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+,d6.s   d5.s,y:(r5)+n5 ; inc A output pointer,d4=nar-(nbr*wr+nbi*wi)=nbr'  
  176.                                                                         ;d3=nbi*wi,d0=nar+(nbr*wr+nbi*wi)=nar',                        PUT ngai' 
  177. _end_grp
  178.       move     n2,d0.l                                            ;n2 is # of group -> d0
  179.       lsl      d0      n0,d1.l                                  ;double n2 # of group,d1=offset of A or B
  180. _end_pass
  181. ;
  182. ; next to last pass
  183. ;
  184.       move      d0.l,n2                                            ;n2= # of group/2
  185.       move      r2,r0                                            ;r0 pointer of A, points to the first data
  186.       move      r0,r4                                            ;r4 pointer of A',points to the first data 
  187.       lea      (r0+2),r1                                        ;r1 pointer of B
  188.       move      r1,r5                                            ;r5 pointer of B'
  189.       move      m2,r6                                            ;the first twiddle factor
  190.       move      #3,n0                                  ;offset of A
  191.       move      n0,n1                                            ;offset of B  
  192.       move      n0,n4                                            ;offset of A'
  193.       move      n0,n5                                            ;offset of B'
  194.       move                              x:(r6)+n6,d9.s  y:,d8.s
  195.       move                                              y:(r1),d7.s
  196.       fmpy.s    d8,d7,d3                  x:(r1)+,d6.s
  197.       fmpy.s    d9,d6,d0
  198.       fmpy.s    d9,d7,d1                                  y:(r1),d7.s
  199.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s
  200.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+n1,d6.s
  201.  
  202.       do      n2,_end_next
  203.       fmpy    d9,d6,d0  fsub.s     d1,d2  d0.s,x:(r5)     y:(r0)+,d5.s
  204.       fmpy    d9,d7,d1  faddsub.s d5,d2  d4.s,x:(r4)     y:(r1),d7.s
  205.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s     d2.s,y:(r4)+
  206.       move                              x:(r6)+n6,d9.s  y:,d8.s
  207.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+,d6.s    d5.s,y:(r5)+
  208.       fmpy    d9,d6,d0  fsub.s     d1,d2  d0.s,x:(r5)     y:(r0)+n0,d5.s
  209.       fmpy    d9,d7,d1  faddsub.s d5,d2  d4.s,x:(r4)     y:(r1),d7.s
  210.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s     d2.s,y:(r4)+n4
  211.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+n1,d6.s  d5.s,y:(r5)+n5
  212. _end_next
  213. ;
  214. ; last pass
  215. ;
  216.       move      n2,d0.l                                            ;# previous groups ->d0
  217.       lsl       d0      r2,r0                                    ;update # groups, r0 points to input data A
  218.       move      d0.l,n2                                            ;# stages ->n2
  219.       move      #odata,r4                                   ;r4 points to A' 
  220.       lea       (r0)+,r1                                    ;r1 points to B 
  221.       move      r4,r2                                            ;r2 points to A' 
  222.         move      m2,r6                                       ;r6 points to twiddle factors  
  223.       move      #2,n0                                       ;offset is 2 for A input pointer
  224.       move      n0,n1                                            ;offset is 2 for B input pointer
  225.       lea        (r2)+n2,r5                                   ;r5 points to B' 
  226.       move         #points/4,n4                               ;offset is #points/4 for A output pointer
  227.       move      n4,n5                                            ;offset is #points/4 for B output pointer
  228.       move         #0,m4                                            ;bit reversed addressing for A output pointer
  229.         ;move        (r5)-n5                                            ;predecrement pointer of B'
  230.       move         m4,m5                                            ;bit reversed addressing for B output pointer
  231.  
  232.       move                              x:(r6)+n6,d9.s  y:,d8.s             ;d9=wr,d8=wi
  233.       move                                              y:(r1),d7.s        ;d7=bi
  234.       fmpy.s    d8,d7,d3                  x:(r1)+n1,d6.s                        ;d6=br,d3=bi*wi
  235.       fmpy.s    d9,d6,d0                                                                ;d0=br*wr
  236.       fmpy.s    d9,d7,d1                                  y:(r1),d7.s    ;d1=bi*wr,d7=nbi
  237.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s                            ;d2=br*wi,d0=bi*wi+br*wr,d4=ar
  238.       move                              x:(r6)+n6,d9.s  y:,d8.s            ;d9=nwr,d8=nwi
  239.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+n1,d6.s                        ;d3=nbi*wi,d4=br',d0=ar',d6=nbr
  240.  
  241.       do      n2,_end_last
  242.       fmpy    d9,d6,d0  fsub.s     d1,d2  d0.s,x:(r5)   y:(r0)+n0,d5.s  ;PUT ar'
  243.       fmpy    d9,d7,d1  faddsub.s d5,d2  d4.s,x:(r4)    y:(r1),d7.s        ;PUT br'
  244.       fmpy    d8,d6,d2  fadd.s     d3,d0  x:(r0),d4.s   d2.s,y:(r4)+n4    ;PUT bi'
  245.       move                              x:(r6)+n6,d9.s  y:,d8.s            ;d9=wr,d8=wi
  246.       fmpy    d8,d7,d3  faddsub.s d4,d0  x:(r1)+n1,d6.s  d5.s,y:(r5)+n5 ;PUT ai'
  247. _end_last
  248.  
  249.         endm 
  250.